package style.zcyLeetCode.a_0007_贪心算法;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 金块切割,求最小的sum总和
 */
public class LessMoneySplitGold {
    public static class MinheapCompare implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2; // < 0 o1<o2 负数
        }
    }

    public static int lessMoney(int[] arr) {
        Queue<Integer> pQ = new PriorityQueue<>();
        // 构造小顶堆
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }

        int sum = 0;
        int cur = 0;
        while (pQ.size()>1) {
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }
}
